1. Field of the Invention
The present invention relates generally to cryptography and, more particularly, to exchanging cryptographic keys between two cryptographic units for a single cryptographic session, and to digital signature.
2. Description of the Prior Art
Two mutually-exclusive classes of cryptographic methods and protocols are well recognized by those familiar with cryptography, symmetric cryptography and public-key cryptography. In symmetric cryptographic protocols, the same key and cryptographic method are used both for encrypting a plaintext message into cyphertext, and for decrypting a cyphertext to recover the plaintext. It is readily apparent that the security of a symmetric cryptographic protocol can never exceed the security of the single key used both for encryption and decryption.
In conventional public-key cryptographic protocols there are two keys, a public key to which anyone can gain access and which is used only for encrypting a plaintext message, and a private key which only the recipient possesses and which is used only for decrypting a cyphertext. For such a public-key cryptographic protocol to be secure it must be unfeasible to determine the private key by analyzing the public key. While public-key cryptographic systems appear alluring, thus far in practice it has been observed that public-key cryptographic methods are significantly slower than symmetric cryptographic methods. In general, it has been found that public-key cryptographic methods are 1000 times slower than symmetric cryptographic methods. Furthermore, present public key cryptographic methods rely upon difficult but solvable mathematical problems, e.g. factoring large integers or discrete logarithms. Such techniques, while providing some security, can be broken by a cryptanalytic attack that is less exhausting than a brute force attack.
Managing the distribution of cryptographic keys is the most difficult security problem in using cryptography both for symmetric protocols and for public-key protocols. Developing secure cryptographic methods and protocols is not easy, but making sure the keys used with such methods and protocols remain secret is an even more difficult task. “Cryptanalysts often attack both symmetric and public-key cryptosystems through their key management.” Schneier, Applied Cryptography, Second Edition© 1996 Bruce Schneier (“Schneier”) p. 169.
For symmetric cryptographic protocols, there are three well recognized key management problems. First, a key may be compromised which permits an eavesdropper who obtains the key either to read all the cyphertext, or even to broadcast bogus cyphertext. The only way to alleviate this problem is to change keys frequently. A second problem for symmetric cryptography key management is that it requires a large number of keys if each pair of individuals in a group is to communicate using a different key. Forty-five unique keys are required if a group of 10 individuals are to communicate. Fifty-five unique keys are required for communication among a group of 11 individuals. The final problem for key management in symmetric cryptographic protocols is that, since keys are more valuable than the encrypted messages, the keys must be exchanged by a secure communication. One approach for securely distributing keys of a symmetric cryptographic protocol is to distribute them using a public-key cryptographic protocol.
Whether used with a symmetric cryptographic protocol or with a public-key cryptographic protocol, an encryption key should not be used indefinitely. First, the longer a key is used the more likely it will be compromised by theft, luck, extortion, bribery or cryptanalysis. Extended use of a key aids an eavesdropper because that provides more cyphertext encoded with the same key to which cryptoanalytic methods may be applied. Second, in general the longer a key is used the greater the loss if the key is compromised. Accordingly, it is not uncommon to encrypt each individual communication using a separate, session key that is used throughout only one particular communication session.
Schneier at pp. 41–68 provides an overview of protocols for digital signatures, key exchange, and authentication. Schneier at pp. 513–522 describes in greater detail various key exchange protocols that may be used to establish a session key including:                1. Shamir's Three-Pass protocol which does not use any secret or public keys;        2. a COMSET protocol which uses a public key technique that is equivalent to factoring a large integer; and        3. an Encrypted Key Exchange (“EKE”) protocol that may be implemented with various different cryptographic methods such as:                    a. a Rivest, Shamir and Adleman (“RSA”) public-key cryptographic method that is described in U.S. Pat. No. 4,405,829;            b. an ElGamal public-key cryptographic method; and            c. a Diffie-Hellman public-key cryptographic method that is described in U.S. Pat. No. 4,200,770.U.S. Pat. Nos. 4,405,829 and 4,200,770 together with Schneier are hereby incorporated by reference.                        
While all of the preceding protocols provide some security for establishing a symmetric cryptographic key, the various protocols require exchanging several, time consuming communications between the parties to establish the key. Moreover, those protocols which require using a public-key cryptographic method also suffer from the slowness of such methods. Furthermore, the preceding key exchange protocols are no more secure than the cryptographic method which they employed for key exchange, all of which can be broken by cryptanalysis that is less exhausting than a brute force attack.
Protocols for key exchange have been developed that are secure against all but a brute force cryptanalytic attack. U.S. Pat. No. 5,583,939 (“the '939 patent”) describes an exchange protocol which establish a session key useful for symmetric cryptography:                1. employing known and publicly identified mathematical functions; and        2. applied to exclusively private data, e.g. numbers.In establishing this one-time key, an eavesdropper can learn both some of the numerical values selected by the parties in establishing the key, and also learn some of the numerical values computed using the known and publicly identified mathematical functions. The method disclosed in the '939 patent requires that the four known and publicly identified mathematical functions possess no inverse. That is, the four known and publicly identified functions must possess the property that knowing one of the quantities used in calculating a quantity and the calculated quantity, it is mathematically impossible to compute the other quantity used in performing the calculation. While the method disclosed in the '939 patent is swifter and simpler than previous methods, it requires initially transmitting at least two quantities between the sender and the receiver, followed by a single quantity between the receiver and the sender.        
Another U.S. Pat. No. 5,987,130 (“the '130 patent”) also describes an exchange protocol which establish a one-time key for use in symmetric cryptography:                1. employing known and publicly identified mathematical functions; and        2. applied to exclusively private data, i.e. numbers.One of the ways in which the method for establishing a one-time key described in the '130 differs from that described in the '939 patent is that an eavesdropper cannot learn any numerical value selected by the parties in establishing the key. That is, the eavesdropper can learn only some of the numerical values computed using the known and publicly identified mathematical functions.        
For the key exchange protocol described in the '130 patent a first of two cryptographic units “T” and “R” wishing to establish a cryptographic key “K” initially selects a first quantity “A”. That same unit then uses a first mathematical function “Φ1” and the selected quantity “A” to compute a second quantity “B”=Φ1(A). The computed quantity B and the function Φ1 must posses the property that knowing the computed quantity B, and the function Φ1, it is mathematically impossible to compute the selected quantity A. That same unit then uses a second mathematical function “Φ2” and the selected quantity “A” to compute a third quantity “C”=Φ2(A). The first unit T or R which selected the quantity A then transmits the computed quantity B to the other, second unit R or T, while retaining at the first unit T or R the computed quantity C.
Upon receiving the quantity B transmitted by the first unit T or R, the second unit R or T first selects a fourth quantity “D.” Then using a third mathematical function Φ3 together with the selected quantity D, the second unit T or R computes a fifth quantity “E”=Φ3(D). The computed quantity E and the function Φ3 must possess the property that knowing the computed quantity E, and the function Φ3, it is mathematically impossible to compute the selected quantity D. That same unit then using a fourth mathematical function Φ4 together with the selected quantity D computes a sixth quantity “F”=Φ4(D). The second unit R or T which selected the quantity D then transmits the computed quantity E to the other, first unit T or R, while retaining at the second unit R or T the computed quantity F.
Then the second unit R or T uses a fifth mathematical function “Ψ2” together with the calculated quantity F and the received quantity B to compute the key “K”=Ψ2(F, B)=Ψ2(Φ4{D}, Φ1{A}). The first unit T or R upon receiving the quantity E transmitted by the unit R or T then uses a sixth mathematical function Ψ1 together with the calculated quantity C and the received quantity E to compute the key “K”=Ψ1(C, E)=Ψ1(2{A}, Φ3{D})=Ψ2(Φ4{D}, Φ1{A}).
While the key exchange protocols disclosed both in the '939 and '130 patents permit establishing a session key for symmetric cryptography that an eavesdropper cannot crack except by using a brute force attack, it has not been possible to extend the disclosed techniques for use in digital signatures. The inability to extend the techniques disclosed in the '939 and '130 patents to digital signature appears to arise because the techniques disclosed there avoid using any pre-published, publicly available information in establishing the symmetric cryptographic key. Stated another way, while establishing the cryptographic key each party sends information to the other party on only one occasion, and therefor neither party publishes any information, other than the mathematical functions and the protocol for their use, before establishing the cryptographic key.